package _dp_base;

/**
 * 256. 粉刷房子
 */
public class No256 {
    private int[][] costs;
    private int[][] cache;

    /**
     * 1. 递归
     */
    public int minCost1(int[][] costs) {
        this.costs = costs;
        int n = costs.length;
        cache = new int[n][3];

        return Math.min(dfs(n - 1, 0), Math.min(dfs(n - 1, 1), dfs(n - 1, 2)));
    }

    private int dfs(int i, int j) {
        if (i == 0) return costs[i][j];
        else if (cache[i][j] != 0) return cache[i][j];
        else if (j == 0) return cache[i][j] = Math.min(dfs(i - 1, 1), dfs(i - 1, 2)) + costs[i][j];
        else if (j == 1) return cache[i][j] = Math.min(dfs(i - 1, 0), dfs(i - 1, 2)) + costs[i][j];
        else return cache[i][j] = Math.min(dfs(i - 1, 0), dfs(i - 1, 1)) + costs[i][j];
    }

    /**
     * 2. 迭代
     */
    public int minCost2(int[][] costs) {
        int n = costs.length;

        int[][] f = new int[n][3];
        f[0][0] = costs[0][0];
        f[0][1] = costs[0][1];
        f[0][2] = costs[0][2];
        for (int i = 1; i < n; i++) {
            f[i][0] = Math.min(f[i - 1][1], f[i - 1][2]) + costs[i][0];
            f[i][1] = Math.min(f[i - 1][0], f[i - 1][2]) + costs[i][1];
            f[i][2] = Math.min(f[i - 1][0], f[i - 1][1]) + costs[i][2];
        }

        return Math.min(f[n - 1][0], Math.min(f[n - 1][1], f[n - 1][2]));
    }

    /**
     * 4. 一维数组
     */
    public int minCost4(int[][] costs) {
        int n = costs.length;

        int[] f = new int[3];
        int pre0 = f[0] = costs[0][0], pre1 = f[1] = costs[0][1], pre2 = f[2] = costs[0][2];
        for (int i = 1; i < n; i++) {
            f[0] = Math.min(pre1, pre2) + costs[i][0];
            f[1] = Math.min(pre0, pre2) + costs[i][1];
            f[2] = Math.min(pre0, pre1) + costs[i][2];
            pre0 = f[0];
            pre1 = f[1];
            pre2 = f[2];
        }

        return Math.min(f[0], Math.min(f[1], f[2]));
    }
}
